package pers.vic.basics.algorithm.dp;

import java.util.logging.Level;

/**
 * @author Vic.xu
 * @description: 最小路径和 {@link A_01_frog} 动态规划
 * {@literal https://leetcode-cn.com/problems/minimum-path-sum/}
 * @date: 2020/11/12 0012 11:41
 */
public class A_03_minPathSum_leetcode64 {
    /*
    给定一个包含非负整数的 m x n 网格 grid ，
    请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
    说明：每次只能向下或者向右移动一步。
     */

    /**
     * 依然参见{@link A_01_frog} 动态规划三步骤
     * 和{@link A_02_uniquePaths_leetcode62} 很类似
     * 1. 定义二维数组dp[m][n] 表示到当前坐标最小值
     * 2. 找出关系：dp[m][n] 最小值 为上面
     * 3. 初始值：第一行和第一列 分别是累加出来的
     */
    public static int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        //初始化 第一列和第一行
        for (int i = 1; i < m; i++) {
            dp[i][0] = grid[i][0] + dp[i-1][0];
        }

        for (int i = 1; i < n; i++) {
            dp[0][i] = grid[0][i] + dp[0][i-1];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[m-1][n-1];
    }


    public static void main(String[] args) {
        int[][] arr = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        //输出: 7路径 1→3→1→1→1 的总和最小
        System.out.println(minPathSum(arr));
    }
}
